package test3.recursion;

/**
 * 779. 第K个语法符号
 * 在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。
 * 给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）
 */
public class KthGrammar {
    public static void main(String[] args) {
        int i = new KthGrammar().kthGrammar(3, 2);
        System.out.println(i);
    }

    public int kthGrammar(int n, int k) {
        if (n == 1 || n == 0) {
            return 0;
        }
        int tmp = (int) Math.pow(2, n - 2);
        if (k <= tmp) {
            return kthGrammar(n - 1, k);
        } else {
            return kthGrammar(n - 1, k - tmp) == 1 ? 0 : 1;
        }
    }
}
